/*
    博弈类问题必备内容详解-下

    前置知识: 
    讲解005、042 - 对数器、对数器打表找规律，一定要看
    讲解030 - 异或运算
    讲解066、067、068、069 - 动态规划基础
    讲解095 - 博弈类问题必备内容详解-上，想听懂本节课，一定要掌握上节课的巴什博弈、尼姆博弈

    博弈专题分为上、下两期，本期为下期，本期视频的最后会讲一个故事

    上期为经典博弈问题的讲解 : 
    巴什博弈(Bash)、尼姆博弈(Nim)、斐波那契博弈(Fibonacci)、威佐夫博弈(Wythoff)
    通过这些讲解会发现，这些博弈问题在考场上要临时想清楚是不太可能的，所以需要下期内容

    下期为SG函数、SG定理的内容，大多数博弈类问题都可以根据SG定理来解决
    这才是最重要的！因为你不可能学完所有的博弈，但是你能具备解决博弈类问题的通用技巧

    ================================================

    图游戏的概念
    任何局面都认为是图中的点，每一个局面都可以通过一种行动，走向图中的下一个点
    如果当前行动有若干个，那么后继节点就有若干个。最终，必败局面的点认为不再有后继节点
    那么公平组合游戏（ICG），就可以对应成一张图

    SG函数(Sprague-Grundy函数），如下是SG返回值的求解方式，俗称mex过程
    最终必败点是A，规定SG(A) = 0
    假设状态点是B，那么SG(B) = 查看B所有后继节点的sg值，其中没有出现过的最小自然数
    SG(B) != 0，那么状态B为必胜态；SG(B) == 0，那么状态B为必败态

    SG定理(Bouton定理)
    如果一个ICG游戏（总），由若干个独立的ICG子游戏构成（分1、分2、分3..)，那么：
    SG(总) = SG(分1) ^ SG(分2) ^ SG(分3)..  任何ICG游戏都是如此，正确性证明类似尼姆博弈
    当数据规模较大时，要善于通过对数器的手段，打印SG表并观察，看看能不能发现简洁规律

    ================================================

    题目1
    SG函数求解过程展示
    巴什博弈
    一共有n颗石子，两个人轮流拿，每次可以拿1~m颗石子
    拿到最后一颗石子的人获胜，根据n、m返回谁赢
    对数器验证

    通过观察sg表，一样可以得到巴什博弈最简洁的结论

    ================================================

    题目2
    SG定理用法展示
    尼姆博弈
    一共有 n 堆石头，两人轮流进行游戏
    在每个玩家的回合中，玩家需要 选择任一 非空 石头堆，从中移除任意 非零 数量的石头
    如果不能移除任意的石头，就输掉游戏
    返回先手是否一定获胜
    对数器验证

    通过观察sg表，以及分析总游戏的异或结果，一样可以得到尼姆博弈最简洁的结论

    ================================================

    题目3
    两堆石头的巴什博弈
    有两堆石头，数量分别为a、b
    两个人轮流拿，每次可以选择其中一堆石头，拿1~m颗
    拿到最后一颗石子的人获胜，根据a、b、m返回谁赢
    来自真实大厂笔试，没有在线测试，对数器验证

    通过观察sg表，以及分析总游戏的异或结果，一样可以得到最简洁的结论

    ================================================

    题目4
    三堆石头拿取斐波那契数博弈
    有三堆石头，数量分别为a、b、c
    两个人轮流拿，每次可以选择其中一堆石头，拿取斐波那契数的石头
    拿到最后一颗石子的人获胜，根据a、b、c返回谁赢
    来自真实大厂笔试，每堆石子的数量在10^5以内
    没有在线测试，对数器验证

    通过观察sg表，很难得到最简洁的结论，索性不优化了，反正数据量允许

    ================================================

    题目5
    E&D游戏
    桌子上有2n堆石子，编号为1、2、3...2n
    其中1、2为一组；3、4为一组；5、6为一组...2n-1、2n为一组
    每组可以进行分割操作：
    任取一堆石子，将其移走，然后分割同一组的另一堆石子
    从中取出若干个石子放在被移走的位置，组成新的一堆
    操作完成后，组内每堆的石子数必须保证大于0
    显然，被分割的一堆的石子数至少要为2
    两个人轮流进行分割操作，如果轮到某人进行操作时，所有堆的石子数均为1，判此人输掉比赛
    返回先手能不能获胜
    测试链接 : https://www.luogu.com.cn/problem/P2148

    通过观察sg表，确实有最简洁的结论，但是也太难观察了吧！多练！以后遇到类似的就会了！

    ================================================

    题目6
    分裂游戏
    一共有n个瓶子，编号为0 ~ n-1，第i瓶里装有nums[i]个糖豆，每个糖豆认为无差别
    有两个玩家轮流取糖豆，每一轮的玩家必须选i、j、k三个编号，并且满足i < j <= k
    当前玩家从i号瓶中拿出一颗糖豆，分裂成两颗糖豆，并且往j、k瓶子中各放入一颗，分裂的糖豆继续无差别
    要求i号瓶一定要有糖豆，如果j == k，那么相当于从i号瓶中拿出一颗，向另一个瓶子放入了两颗
    如果轮到某个玩家发现所有糖豆都在n-1号瓶里，导致无法行动，那么该玩家输掉比赛
    先手希望知道，第一步如何行动可以保证自己获胜，要求返回字典序最小的行动
    第一步从0号瓶拿出一颗糖豆，并且往2、3号瓶中各放入一颗，可以确保最终自己获胜
    第一步从0号瓶拿出一颗糖豆，并且往11、13号瓶中各放入一颗，也可以确保自己获胜
    本题要求每个瓶子的编号看做是一个字符的情况下，最小的字典序，所以返回"0 2 3"
    如果先手怎么行动都无法获胜，返回"-1 -1 -1"
    先手还希望知道自己有多少种第一步取糖的行动，可以确保自己获胜，返回方法数
    测试链接 : https://www.luogu.com.cn/problem/P3185

*/